package dp;

/**
 * 力扣数硬币那题
 */
public class CoinCount {
    public int coinChange(int[] coins, int amount) {
        //创建备忘录
        int[] table = new int[amount+1];
        int res = dp(table,coins,amount);
        return res;
    }

    /**
     * 明确动态规划函数的输入输出
     * 输入就是目标金额
     * 而输出就是该金额所需要的最少硬币数。
     * 动态规划题，使用分解子问题的思路。目标金额为11元，那么十元所需要的最小硬币数是多少，9元呢？6元呢？
     * 得到他们最小的硬币数，加个1，即可得到最小值。
     * @param coins
     * @param amount
     * @return
     */
    public int dp(int[] table,int[] coins,int amount){


        //baseCase
        if (amount==0){
            return 0;
        }

        if (amount<0){
            return -1;
        }

        if (table[amount]!=0){
            return table[amount];
        }

        int res = Integer.MAX_VALUE;

        for (int coin : coins) {
            //做出选择
            int subProblem = dp(table,coins, amount-coin);
            //返回-1，说明该子问题无解，不能让他参与更新数据
            if (subProblem==-1){
                continue;
            }
            //更新最小值
            res = Math.min(res,subProblem+1);
        }

        /**
         * 原来这个返回的写法有问题，假如说amount=7，coin数组为[3,6]
         * 那么这个递归树中的子节点返回的基本上全是-1
         * 而返回-1时我们不会对table进行修改，table[amount]还是0，下次碰到这个子问题，又要重新计算一遍
         * 这个故事告诉我们table得如实记录dp递归函数的返回值
         */
        /*if (res!=Integer.MAX_VALUE){
            table[amount]=res;
            return res;
        }else {
            return -1;
        }*/
        if (res!=Integer.MAX_VALUE){
            table[amount]=res;
            return res;
        }else {
            table[amount]=-1;
            return -1;
        }
    }

    public static void main(String[] args) {
        CoinCount coinCount = new CoinCount();
        int [] coins = new int[3];
        coins[0]=1;
        coins[1]=2;
        coins[2]=5;

        int count = coinCount.coinChange(coins, 11);
        System.out.println("count = " + count);
    }


}
